Làm thế nào để mô tả toán học những sợi dây vô hình kết nối xã hội? Dù là các số Bacon kết nối Bela Lugosi với các biểu tượng Hollywood hay Số Bacon kết nối Bela Lugosi với các biểu tượng Hollywood hay Đồ thị tương tự phân cụm các điểm dữ liệu dựa trên độ gần gũi, Thuyết đồ thị cung cấp ngôn ngữ chính thức $G = (V, E)$ để mô hình hóa những vũ trụ rời rạc này.
1. Cấu tạo của đồ thị
Ở cốt lõi, một đồ thị gồm một tập hợp đỉnh ($V$) và một tập hợp cạnh ($E$). Tuy nhiên, quy tắc tham gia thay đổi tùy theo cấu trúc:
- Đồ thị đơn: Dạng tinh tế nhất; nó cấm vòng lặp (cạnh nối một đỉnh với chính nó) và cạnh song song (cạnh thừa giữa hai điểm giống nhau).
- Đồ thị đa: Cho phép vòng lặp và cạnh song song, thường dùng để mô hình hóa nhiều loại tương tác khác nhau (ví dụ: tin nhắn so với cuộc gọi) giữa hai nút giống nhau.
- Đỉnh cô lập: Một đỉnh $v$ được gọi là cô lập nếu không có cạnh nào nối vào nó, đại diện cho một đối tượng không có mối quan hệ nào trong tập hiện tại.
Trong khoa học dữ liệu, chúng ta thường sử dụng một Hàm bất tương đồng để xây dựng đồ thị:
$$s(v, w) = |p_1 - q_1| + |p_2 - q_2| + |p_3 - q_3|$$
Chúng ta chỉ vẽ một cạnh giữa $v$ và $w$ nếu $s(v, w)$ nhỏ hơn một ngưỡng nhất định, hiệu quả tạo ra một mạng lưới các "hàng xóm".
2. Đường đi, tính liên thông và thành phần
Một đường đi là một dãy các đỉnh và cạnh. Nếu một đường đi không đi qua bất kỳ đỉnh nào quá một lần, thì nó là một đường đi đơn. Tính liên thông là nhịp đập của đồ thị:
- Đồ thị liên thông: Một đường đi tồn tại giữa mọi cặp đỉnh trong đồ thị.
- Thành phần: Nếu một đồ thị không liên thông, nó sẽ bị tách thành các phần rời rạc gọi là thành phần. Mỗi thành phần là một đồ thị con liên thông tối đa.
3. Đồ thị con: Kiến trúc của các tập con
Một đồ thị con $G' = (V', E')$ là một tập con của đồ thị $G$ sao cho mọi đỉnh trong $V'$ đều tồn tại trong $V$, và mọi cạnh trong $E'$ nối các đỉnh nằm trong $V'$. Việc xác định các đồ thị con là điều quan trọng để phát hiện các mẫu cục bộ trong các mạng lưới toàn cầu.